In a portable communication system, users carry low power, low cost, portable digital radio telephone terminals from place to place during and between calls.
Some portable terminals employ a Digital Signal Processor to implement the complicated algorithms that are needed to code speech at low bit rate. Other portable terminals utilize a custom chip for the low bit rate encoding of speech and include a low power microcontroller for handling signalling protocols and other miscellaneous tasks. In either case, a portable terminal must operate for long periods of time on small batteries and a low power implementation of all signal processing operations inside the portable terminal is important. Accordingly, there is a limit on the complexity of any signal processing operation which can take place inside the portable terminal in a short period of time.
In a portable communication system, the portable radio terminals access the local telephone exchange network via a suitably dense matrix of shoebox sized radio ports which are located on utility poles or in buildings. Each port comprises a radio modem. Each port is in turn connected back to the telephone network switching system by way of server in the form of a port control unit which may be located in a central office building. A port control unit performs a variety of processing functions including converting between a format suitable for use on the radio link between the portable terminal and the radio ports and a format suitable for use in the telephone network switching system.
The portable communication system may be described as being computationally asymmetric. By this it is meant that each connection has a computationally weak party in the form of the terminal--i.e., a party with small computational resources--and a computationally strong party in the form of the server--i.e., a party with large computational resources. Thus algorithms which are used in such an asymmetric system should preferably be computationally asymmetric, i.e., the algorithm should require only a minimum of processing on the computationally weak side while more substantial processing is performed on the computationally strong side.
Because a portable communication system transmits conversations between portable telephone terminals and an array of fixed location ports via radio, the conversations of a portable communication system are more susceptible to eavesdropping than are the conversations of a wireline network.
In addition, unlike wireline telephones, which are tied to a particular wire pair on a particular network, portable telephone terminals roam from place to place and access the network via different ports at different times. The lack of association between user and particular physical location can make a portable communication system vulnerable to attempts at the fraudulent acquisition of services.
The present invention is particularly concerned with message encryption (i.e., the encryption of conversation content), key agreement and distribution (i.e. distribution of the keys required by message encryption techniques) and authentication (i.e. ensuring that a service request is legitimate). In particular, the present invention is concerned with foiling the eavesdropper, i.e., one who utilizes radio equipment to intercept the radio transmissions between the portable terminals and the ports.
Another problem which characterizes portable communication systems is the problem of user traceability. Specifically, if a user transmits identifying information in the clear, it is possible for an eavesdropper to determine the location of the user, so that privacy with respect to a user's location is not maintained. The present invention also relates to maintaining the privacy of a user location.
Eavesdropping can be thwarted through the use of a message encryption technique. A message encryption technique employs an encipherment function which utilizes a number referred to as a session key to encipher data (e.g., conversation content). Only the portable terminal and the specific port control unit with which the portable terminal is in communication should have knowledge of the session key, so that only the proper portable terminal and the port control unit, as paired on a particular conversation, can encrypt and decrypt digital signals. Two examples of encipherment functions are the National Bureau of Standards Data Encryption Standard (DES) (see e.g., National Bureau of Standards, "Data Encryption Standard", FIPS-PUB-45, 1977) and the more recent Fast Encipherment Algorithm (FEAL) (see e.g., Shimizu and S. Miyaguchi, "FEAL-Fast Data Encipherment Algorithm," Systems and Computers in Japan, Vol. 19, No. 7, 1988 and S. Miyaguchi, "The FEAL Cipher Family", Proceedings of CRYPTO '90, Santa Barbara, Calif., August, 1990). One way to use an encipherment function is the electronic codebook technique. In this technique a plain text message m is encrypted to produce the cipher text message c using the encipherment function f by the formula c=f(m,sk) where sk is a session key. The cipher text message c can only be decrypted with the knowledge of the session key sk to obtain the plain text message m=f.sup.-1 (c,sk).
One problem with the use of the encipherment functions such as DES and FEAL in a portable communication system is the problem of session key agreement.
In the conventional session key agreement technique, each portable terminal i has a secret key k.sub.i known only to it and a cryptographic database DB. Similarly, each port control unit j has a secret key k.sub.j, known only to it and the cryptographic database DB. At the start of a communication session, the portable terminal i sends a service request and its identity i in the clear to a port control unit j. The port control unit sends the pair (i,j) to the cryptographic database DB. The DB picks a random session key sk and sends to the port control unit j the pair c.sub.i,c.sub.j where c.sub.i =f(k.sub.i,sk) and c.sub.j =f(k.sub.j,sk). The port control unit j deciphers c.sub.j to find sk and sends c.sub.i to the portable terminal i. The portable terminal i deciphers c.sub.i to find sk. Now both the port control unit j and the portable terminal i are in possession of the session key sk. Thus, enciphered messages c=f(m,sk) can be transmitted back and forth between the portable terminal i and the port control unit j.
This approach has several advantages. First the approach requires minimal power in the portable terminal because it utilizes only conventional cryptography. In particular, the computation power required to evaluate f and f.sup.-1 is quite small.
In addition, the conventional key distribution approach is also self-authenticating because a portable telephone trying to impersonate the portable telephone i must know the ostensibly secret key k.sub.i ahead of time.
On the other hand, the conventional key distribution protocol requires a database of secret cryptographic keys, which is hard to protect and maintain, and adds survivability and reliability problems to the system. A primary weakness is that a potential eavesdropper can obtain the key k.sub.i for the portable telephone i once, and can subsequently intercept all of i's conversations without i knowing about it. This is the worst kind of damage that can occur; undetectable compromise of privacy. Also, the conventional key distribution protocol has a traceability problem. A portable terminal must announce its identity in the clear before a session key can be fetched from the database. Thus, an eavesdropper can determine the location of a particular portable.
Another approach to session key distribution and party authentication in a portable communication system is to use public key cryptographic techniques. In a typical public key cryptographic system, each party i has a public key P.sub.i and a secret key s.sub.i. The public key P.sub.i is known to everyone, but the secret key S.sub.i is known only to party i. A message m to user i is encrypted using a public operation which makes use of the public key known to everyone, i.e., c=P(m,P.sub.i) where c is the encrypted message, m is the clear text message, P.sub.i is the public key and p signifies the public operation. However, this message is decrypted using an operation which makes use of the secret key s.sub.i, i.e., m=s(c,S.sub.i); where s signifies the operation. Only the party i which has the secret key S.sub.i can perform the operation to decrypt the encrypted message.
Public key cryptographic techniques can be used for the distribution of session keys to the parties in a portable communication system. (See the above-identified U.S. patent application, Ser. No. 789,700). Public key cryptographic techniques can also be used for party authentication in a portable communication system.
One way to use public key cryptography for authentication is to use a signature system. If it is true that P(S(m,S.sub.i),P.sub.i)=m, then the owner of the corresponding keys P.sub.i, S.sub.i, could sign message m by producing c=S(m,S.sub.i). The verifier, given m and c will verify m=P(c,P.sub.i). A signature system could be used for verification as follows: If it is well known that party i's public key is P.sub.i and some party claims to be i, challenge the party claiming to be i with message m and ask the party to sign the message m using his secret key s.sub.i ; then verify the signature using P.sub.i.
Another aspect of party authentication relates to authentication of a party's public key P.sub.i. A user claiming to be i can provide his public key provided it is certified by a trusted central authority such as a network administrator. The trusted central authority itself has a well known public key P.sub.u. The certification is a signature of the trusted authority on a linkage between the user's identification i and his public key P.sub.i.
The highest level of security for session key distribution and mutual party authentication based on public key cryptography:
1) avoids the use of an on-line centralized database of secret information,
2) hides the identity of a user from an eavesdropper
3) achieves mutual authentication and session key agreement between the parties, in such a way that they do not exchange any permanent secrets.
To achieve this highest level of security using RSA, the most well-known public key algorithm (see e.g., R. L. Rivest, A. Shamir, L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, vol. 21, no. 2, pp. 120-126, February 1978), each of the parties must perform on the order of 200 large modular multiplications (where the numbers involved are over 500 bits in length). Using the algorithms described in the above-identified U.S. patent application Ser. No. 789,700, this highest level of security requires about 200 modular multiplications.
The problem with these prior art algorithms is that a large amount of computations is required by both parties. This is not suitable in an asymmetric system wherein one side (e.g., the terminal or portable telephone) has only weak computational resources and one side (e.g., the server or port control unit), has strong computational resources. The prior art algorithms are not sufficiently asymmetric so that only a very small amount of computations need to be performed on the weak side.
Accordingly, it is an object of the present invention to provide a public key cryptographic method for key distribution and mutual party authentication with a high level of security in an asymmetric system where one of the parties is computationally weak and the other party is computationally strong.